home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / util / libs / type1beta5.lha / type1 / src / regions.c < prev    next >
C/C++ Source or Header  |  1994-12-17  |  47KB  |  1,758 lines
  1. /* $XConsortium: regions.c,v 1.6 94/02/06 16:22:21 gildea Exp $ */
  2. /* Copyright International Business Machines, Corp. 1991
  3.  * All Rights Reserved
  4.  * Copyright Lexmark International, Inc. 1991
  5.  * All Rights Reserved
  6.  *
  7.  * License to use, copy, modify, and distribute this software and its
  8.  * documentation for any purpose and without fee is hereby granted,
  9.  * provided that the above copyright notice appear in all copies and that
  10.  * both that copyright notice and this permission notice appear in
  11.  * supporting documentation, and that the name of IBM or Lexmark not be
  12.  * used in advertising or publicity pertaining to distribution of the
  13.  * software without specific, written prior permission.
  14.  *
  15.  * IBM AND LEXMARK PROVIDE THIS SOFTWARE "AS IS", WITHOUT ANY WARRANTIES OF
  16.  * ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO ANY
  17.  * IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE,
  18.  * AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.  THE ENTIRE RISK AS TO THE
  19.  * QUALITY AND PERFORMANCE OF THE SOFTWARE, INCLUDING ANY DUTY TO SUPPORT
  20.  * OR MAINTAIN, BELONGS TO THE LICENSEE.  SHOULD ANY PORTION OF THE
  21.  * SOFTWARE PROVE DEFECTIVE, THE LICENSEE (NOT IBM OR LEXMARK) ASSUMES THE
  22.  * ENTIRE COST OF ALL SERVICING, REPAIR AND CORRECTION.  IN NO EVENT SHALL
  23.  * IBM OR LEXMARK BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  24.  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
  25.  * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
  26.  * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
  27.  * THIS SOFTWARE.
  28.  */
  29.  
  30. /*
  31.  * REGIONS Module - Regions Operator Handler
  32.  *
  33.  * This module is responsible for creating and manipulating regions.
  34.  *
  35.  * &author. Jeffrey B. Lotspiech (lotspiech@almaden.ibm.com)
  36.  */
  37.  
  38.  
  39. /*
  40.  * Include Files
  41.  *
  42.  * The included files are:
  43.  */
  44. #ifndef T1GST
  45. #include "global.h"
  46. #endif
  47.  
  48.  
  49. /**
  50.  * Prototypes for static functions
  51.  **/
  52. static struct edgelist *NewEdge(
  53.         pel xmin, int xmax,        /* X extent of edge */
  54.         pel ymin, int ymax,        /* Y extent of edge */
  55.         pel *xvalues,            /* list of X values for entire edge */
  56.         int isdown);            /* flag:  TRUE means edge progresses downward */
  57.  
  58. static struct edgelist *swathxsort(
  59.         struct edgelist *before0,     /* edge before this swath */
  60.         struct edgelist *edge);        /* input edge */
  61.  
  62. static void Unwind(
  63.         struct edgelist *area);    /* input area modified in place */
  64.  
  65. static void __stdargs newfilledge(
  66.         struct region *R,        /* region being built */
  67.         fractpel xmin,
  68.         fractpel xmax,            /* X range of this edge */
  69.         fractpel ymin,
  70.         fractpel ymax,            /* Y range of this edge */
  71.         int isdown);            /* flag:  TRUE means edge goes down, else up */
  72.  
  73. static struct edgelist *splitedge(
  74.         struct edgelist *list,    /* area to split */
  75.         pel y);                    /* Y value to split list at */
  76.  
  77. static void vertjoin(struct edgelist *top, struct edgelist *bottom);
  78. static int touches(int h, pel *left, pel *right);
  79. static int crosses(int h, pel *left, pel *right);
  80. static void cedgemin(int h, pel *e1, pel x);
  81. static void cedgemax(int h, pel *e1, pel x);
  82. static void edgemin(int h, pel *e1, pel *e2);
  83. static void edgemax(int h, pel *e1, pel *e2);
  84. static void discard(struct edgelist *left, struct edgelist *right);
  85. static void edgecheck(struct edgelist *edge, int oldmin, int oldmax);
  86. static void OptimizeRegion(struct region *R);
  87.  
  88.  
  89. /*
  90.  * The ISOPTIMIZED flag tells us if we've put a permanent region in
  91.  * 'optimal' form.
  92.  */
  93. #define   ISOPTIMIZED(flag)    ((flag)&0x10)
  94.  
  95.  
  96. /*
  97.  * "INFINITY" - A Constant Region Structure of Infinite Extent
  98.  *
  99.  * Infinity is the complement of a null area:
  100.  * Note - removed the refcount = 1 init, replaced with references = 2 3-26-91 PNM
  101.  */
  102. //static struct region infinity =
  103. //{
  104. //    REGIONTYPE,
  105. //    ISCOMPLEMENT(ON) + ISINFINITE(ON) + ISPERMANENT(ON) + ISIMMORTAL(ON), 2,
  106. //    0, 0, 0, 0,
  107. //    0, 0, 0, 0,
  108. //    NULL, NULL,
  109. //    0, 0, 0, 0, 0, NULL, NULL,
  110. //    NULL, 0, NULL, NULL
  111. //};
  112. //struct region *INFINITY = &infinity;
  113.  
  114.  
  115. /*
  116.  * "EmptyRegion" - A Region Structure with Zero Area
  117.  *
  118.  * This structure is used to initialize the region to be built in
  119.  * Interior():
  120.  * Note - replaced refcount = 1 init with references = 2 3-26-91 PNM
  121.  */
  122. struct region EmptyRegion =
  123. {
  124.     REGIONTYPE,
  125.     ISPERMANENT(ON) + ISIMMORTAL(ON), 2,
  126.     0, 0, 0, 0,
  127.     MAXPEL, MAXPEL, MINPEL, MINPEL,
  128.     NULL, NULL,
  129.     0, 0, 0, 0, 0, NULL, NULL,
  130.     NULL, 0, NULL, NULL
  131. };
  132.  
  133.  
  134. /*
  135.  * KillRegion() - Destroys a Region
  136.  *
  137.  * KillRegion nominally just decrements the reference count to that region.
  138.  * If the reference count becomes 0, all memory associated with it is
  139.  * freed.  We just follow the linked list, freeing as we go, then kill any
  140.  * associated (thresholded) picture.
  141.  * Note - added conditional return based on references 3-26-91 PNM
  142.  */
  143. void t1_KillRegion(
  144.         struct region *area)    /* area to free */
  145. {
  146.     struct edgelist *p;        /* loop variable */
  147.     struct edgelist *next;    /* loop variable */
  148.  
  149.     if (area->references < 0)
  150.         t1_abort("KillRegion:  negative reference count");
  151.     if ((--(area->references) > 1) ||
  152.         ((area->references == 1) && !ISPERMANENT(area->flag)))
  153.         return;
  154.  
  155.     for (p = area->anchor; p != NULL; p = next)
  156.     {
  157.         next = p->link;
  158.         Free(p);
  159.     }
  160.     if (area->thresholded != NULL)
  161.         KillPicture(area->thresholded);
  162.     Free(area);
  163. }
  164.  
  165.  
  166. /*
  167.  * CopyRegion() - Makes a Copy of a Region
  168.  */
  169. struct region *t1_CopyRegion(
  170.         struct region *area)    /* region to duplicate */
  171. {
  172.     struct region *r;            /* output region built here */
  173.     struct edgelist *last;        /* loop variable */
  174.     struct edgelist *p, *newp;    /* loop variables */
  175.  
  176.     r = (struct region *)Allocate(sizeof(struct region), area, 0);
  177.  
  178.     r->anchor = NULL;
  179.  
  180.     for (p = area->anchor; VALIDEDGE(p); p = p->link)
  181.     {
  182.         newp = NewEdge(p->xmin, p->xmax, p->ymin, p->ymax, p->xvalues, ISDOWN(p->flag));
  183.         if (r->anchor == NULL)
  184.             r->anchor = last = newp;
  185.         else
  186.             last->link = newp;
  187.  
  188.         last = newp;
  189.     }
  190.  
  191.     if (area->thresholded != NULL)
  192.         /* replaced DupPicture with Dup() 3-26-91 PNM */
  193.         r->thresholded = (struct picture *)Dup(area->thresholded);
  194.     return (r);
  195. }
  196.  
  197.  
  198. /*
  199.  * NewEdge() - Allocates and Returns a New "edgelist" Structure
  200.  *
  201.  * We allocate space for the X values contiguously with the 'edgelist'
  202.  * structure that locates them.  That way, we only have to free the
  203.  * edgelist structure to free all memory associated with it.  Damn
  204.  * clever, huh?
  205.  */
  206. static struct edgelist *NewEdge(
  207.         pel xmin, int xmax,        /* X extent of edge */
  208.         pel ymin, int ymax,        /* Y extent of edge */
  209.         pel *xvalues,            /* list of X values for entire edge */
  210.         int isdown)                /* flag:  TRUE means edge progresses downward */
  211. {
  212.     static struct edgelist template =
  213.     {
  214.         EDGETYPE, 0, 1, NULL, NULL,
  215.         0, 0, 0, 0, NULL
  216.     };
  217.  
  218.     struct edgelist *r;            /* returned structure */
  219.     int iy;                        /* ymin adjusted for 'long' alignment purposes */
  220.  
  221.     IfTrace2((RegionDebug), "....new edge: ymin=%d, ymax=%d ", (long)ymin, (long)ymax);
  222.     if (ymin >= ymax)
  223.         t1_abort("newedge: height not positive");
  224.  
  225.     /*
  226.      * We are going to copy the xvalues into a newly allocated area.  It
  227.      * helps performance if the values are all "long" aligned.  We can test
  228.      * if the xvalues are long aligned by ANDing the address with the
  229.      * (sizeof(long) - 1)--if non zero, the xvalues are not aligned well.  We
  230.      * set 'iy' to the ymin value that would give us good alignment:
  231.      */
  232.     iy = ymin - (((int)xvalues) & (sizeof(long) - 1)) / sizeof(pel);
  233.  
  234.     r = (struct edgelist *)Allocate(sizeof(struct edgelist), &template, (ymax - iy) * sizeof(pel));
  235.  
  236.     if (isdown)
  237.         r->flag = ISDOWN(ON);
  238.  
  239.     r->xmin = xmin;
  240.     r->xmax = xmax;
  241.     r->ymin = ymin;
  242.     r->ymax = ymax;
  243.  
  244.     r->xvalues = (pel *) FOLLOWING(r);
  245.     if (ymin != iy)
  246.     {
  247.         r->xvalues += ymin - iy;
  248.         xvalues -= ymin - iy;
  249.     }
  250.  
  251.     /*
  252.      * We must round up (ymax - iy) so we get the ceiling of the number of
  253.      * longs.  The destination must be able to hold these extra bytes because
  254.      * Allocate() makes everything it allocates be in multiples of longs.
  255.      */
  256.     LONGCOPY(&r[1], xvalues, (ymax - iy) * sizeof(pel) + sizeof(long) - 1);
  257.  
  258.     IfTrace1((RegionDebug), "result=%x\n", r);
  259.     return (r);
  260. }
  261.  
  262.  
  263. /*
  264.  * Building Regions
  265.  *
  266.  * Interior() - Iterate Through a Path, Building a Region
  267.  *
  268.  * This routine is the workhorse driver routine that iterates through a
  269.  * path, calling the appropriate stepping routines to actually produce the
  270.  * run end "edgelist" structures.
  271.  *
  272.  * "Interior" calls StepLine or StepConic or StepBezier as appropriate
  273.  * to produce run ends.
  274.  *
  275.  * Occasionally these routines will notice a change in Y direction
  276.  * and will call ChangeDirection (through the GOING_TO macro); this is
  277.  * a call back to the REGIONS module.
  278.  *
  279.  * ChangeDirection will call whatever function is in the region
  280.  * structure; for Interior, this function is 'newfilledge'.
  281.  *
  282.  * Newfilledge will call NewEdge to create a new edgelist structure,
  283.  * then, call SortSwath to sort it onto the linked list being built at
  284.  * the region "anchor".
  285.  *
  286.  * By making the function called by ChangeDirection be a parameter of the
  287.  * region, we allow the same ChangeDirection logic to be used by stroking.
  288.  */
  289. struct region *Interior(
  290.         struct segment *p,        /* take interior of this path */
  291.         int fillrule)            /* rule to follow if path crosses itself */
  292. {
  293.     fractpel x, y;                /* keeps ending point of path segment */
  294.     fractpel lastx, lasty;        /* previous x,y from path segment before */
  295.     struct region *R;            /* region I will build */
  296.     struct segment *nextP;        /* next segment of path */
  297.     struct fractpoint hint;        /* accumulated hint value */
  298.     char tempflag;                /* flag; is path temporary? */
  299.     char Cflag;                    /* flag; should we apply continuity? */
  300.  
  301.     IfTrace2((MustTraceCalls), ".  INTERIOR(%z, %d)\n", p, (long)fillrule);
  302.  
  303.     if (p == NULL)
  304.         return (NULL);
  305.  
  306.     /*
  307.      * Establish the 'Cflag' continuity flag based on user's fill rule and
  308.      * our own 'Continuity' pragmatic (0: never do continuity, 1: do what
  309.      * user asked, >1: do it regardless).
  310.      */
  311.     if (fillrule > 0)
  312.     {
  313.         Cflag = Continuity > 0;
  314.         fillrule -= CONTINUITY;
  315.     }
  316.     else
  317.         Cflag = Continuity > 1;
  318.  
  319.     ARGCHECK((fillrule != WINDINGRULE && fillrule != EVENODDRULE),
  320.         "Interior: bad fill rule", NULL, NULL, (1, p,NULL,NULL), struct region *);
  321.  
  322.     if (p->type == TEXTTYPE)
  323. /*             if (fillrule != EVENODDRULE)
  324.                else */
  325.         return ((struct region *)UniquePath(p));
  326.  
  327.     if (p->type == STROKEPATHTYPE)
  328.         if (fillrule == WINDINGRULE)
  329.             return ((struct region *)DoStroke(p));
  330.         else
  331.             p = CoercePath(p);
  332.  
  333.     R = (struct region *)Allocate(sizeof(struct region), &EmptyRegion, 0);
  334.  
  335.     ARGCHECK(!ISPATHANCHOR(p), "Interior:  bad path", p, R, (0,NULL,NULL,NULL), struct region *);
  336.     ARGCHECK((p->type != MOVETYPE), "Interior:  path not closed", p, R, (0,NULL,NULL,NULL), struct region *);
  337.  
  338.  
  339. /* changed definition from !ISPERMANENT to references <= 1 3-26-91 PNM */
  340.     tempflag = (p->references <= 1);    /* only first segment in path is so marked */
  341.     if (!ISPERMANENT(p->flag))
  342.         p->references -= 1;
  343.  
  344.     R->newedgefcn = newfilledge;
  345.  
  346.     /*
  347.      * Believe it or not, "R" is now completely initialized.  We are counting
  348.      * on the copy of template to get other fields the way we want them,
  349.      * namely
  350.      *
  351.      * anchor = NULL
  352.      * xmin, ymin, xmax, ymax, to minimum and maximum values respectively.
  353.      *
  354.      * Anchor = NULL is very
  355.      * important to ChangeDirection.
  356.      * See CD.
  357.      *
  358.      * To minimize problems of "wrapping" in our pel arithmetic, we keep an
  359.      * origin of the region which is the first move.  Hopefully, that keeps
  360.      * numbers within plus or minus 32K pels.
  361.      */
  362.     R->origin.x = 0 /*TOFRACTPEL(NEARESTPEL(p->dest.x))*/ ;
  363.     R->origin.y = 0 /*TOFRACTPEL(NEARESTPEL(p->dest.y))*/ ;
  364.     lastx = -R->origin.x;
  365.     lasty = -R->origin.y;
  366.  
  367.     /*
  368.      * ChangeDirection initializes other important fields in R, such as
  369.      * lastdy, edge, edgeYstop, edgexmin, and edgexmax.  The first segment
  370.      * is a MOVETYPE, so it will be called first.
  371.      */
  372.  
  373.     /*
  374.      * The hints data structure must be initialized once for each path.
  375.      */
  376.     if (ProcessHints)
  377.         InitHints();    /* initialize hint data structure */
  378.  
  379.     while (p != NULL)
  380.     {
  381.  
  382.         x = lastx + p->dest.x;
  383.         y = lasty + p->dest.y;
  384.  
  385.         IfTrace2((HintDebug > 0), "Ending point = (%p,%p)\n", x, y);
  386.  
  387.         nextP = p->link;
  388.  
  389.         /*
  390.          * Here we start the hints processing by initializing the hint value to
  391.          * zero.  If ProcessHints is FALSE, the value will remain zero.
  392.          * Otherwise, hint accumulates the computed hint values.
  393.          */
  394.         hint.x = hint.y = 0;
  395.  
  396.         /*
  397.          * If we are processing hints, and this is a MOVE segment (other than
  398.          * the first on the path), we need to close (reverse) any open hints.
  399.          */
  400.         if (ProcessHints)
  401.             if ((p->type == MOVETYPE) && (p->last == NULL))
  402.             {
  403.                 CloseHints(&hint);
  404.                 IfTrace2((HintDebug > 0), "Closed point= (%p,%p)\n",
  405.                      x + hint.x, y + hint.y);
  406.             }
  407.  
  408.         /*
  409.          * Next we run through all the hint segments (if any) attached to this
  410.          * segment.  If ProcessHints is TRUE, we will accumulate computed hint
  411.          * values.  In either case, nextP will be advanced to the first non-HINT
  412.          * segment (or NULL), and each hint segment will be freed if necessary.
  413.          */
  414.         while ((nextP != NULL) && (nextP->type == HINTTYPE))
  415.         {
  416.             if (ProcessHints)
  417.                 ProcessHint(nextP, x + hint.x, y + hint.y, &hint);
  418.  
  419.             {
  420.                 register struct segment *saveP = nextP;
  421.  
  422.                 nextP = nextP->link;
  423.                 if (tempflag)
  424.                     Free(saveP);
  425.             }
  426.         }
  427.  
  428.         /*
  429.          * We now apply the full hint value to the ending point of the path segment.
  430.          */
  431.         x += hint.x;
  432.         y += hint.y;
  433.  
  434.         IfTrace2((HintDebug > 0), "Hinted ending point = (%p,%p)\n", x, y);
  435.  
  436.         switch (p->type)
  437.         {
  438.  
  439.         case LINETYPE:
  440.             StepLine(R, lastx, lasty, x, y);
  441.             break;
  442.  
  443.         case CONICTYPE:
  444.             {
  445.             /*
  446.              * For a conic curve, we apply half the hint value to the conic midpoint.
  447.              */
  448.             }
  449.             break;
  450.  
  451.         case BEZIERTYPE:
  452.             {
  453.                 register struct beziersegment *bp = (struct beziersegment *)p;
  454.  
  455.             /*
  456.              * For a Bezier curve, we apply the full hint value to the Bezier C point.
  457.              */
  458.                 StepBezier(R, lastx, lasty,
  459.                        lastx + bp->B.x, lasty + bp->B.y,
  460.                        lastx + bp->C.x + hint.x,
  461.                        lasty + bp->C.y + hint.y,
  462.                        x, y);
  463.             }
  464.             break;
  465.  
  466.         case MOVETYPE:
  467.             /*
  468.              * At this point we have encountered a MOVE segment.  This breaks the
  469.              * path, making it disjoint.
  470.              */
  471.             if (p->last == NULL)    /* i.e., not first in path */
  472.                 ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
  473.  
  474.             ChangeDirection(CD_FIRST, R, x, y, (fractpel) 0);
  475.  
  476.             /*
  477.              * We'll just double check for closure here.  We forgive an appended
  478.              * MOVETYPE at the end of the path, if it isn't closed:
  479.              */
  480.             if (!ISCLOSED(p->flag) && p->link != NULL)
  481.                 return ((struct region *)ArgErr("Fill: sub-path not closed", p, NULL));
  482.             break;
  483.  
  484.         default:
  485.             t1_abort("Interior: path type error");
  486.         }
  487.  
  488.         /*
  489.          * We're done with this segment.  Advance to the next path segment in
  490.          * the list, freeing this one if necessary:
  491.          */
  492.         lastx = x;
  493.         lasty = y;
  494.  
  495.         if (tempflag)
  496.             Free(p);
  497.         p = nextP;
  498.     }
  499.     ChangeDirection(CD_LAST, R, lastx, lasty, (fractpel) 0);
  500.     R->ending.x = lastx;
  501.     R->ending.y = lasty;
  502.  
  503.     /*
  504.      * Finally, clean up the region's based on the user's 'fillrule' request:
  505.      */
  506.     if (Cflag)
  507.         ApplyContinuity(R);
  508.     if (fillrule == WINDINGRULE)
  509.         Unwind(R->anchor);
  510.     return (R);
  511. }
  512.  
  513.  
  514. /*
  515.  * Unwind() - Discards Edges That Fail the Winding Rule Test
  516.  *
  517.  * The winding rule says that upward going edges should be paired with
  518.  * downward going edges only, and vice versa.  So, if two upward edges
  519.  * or two downward edges are nominally left/right pairs, Unwind() should
  520.  * discard the second one.  Everything should balance; we should discard
  521.  * an even number of edges; of course, we abort if we don't.
  522.  */
  523. static void Unwind(
  524.         struct edgelist *area)        /* input area modified in place */
  525. {
  526.     struct edgelist *last, *next;    /* struct before and after current one */
  527.     int y;                            /* ymin of current swath */
  528.     int count, newcount;            /* winding count registers */
  529.  
  530.     IfTrace1((RegionDebug > 0), "...Unwind(%z)\n", area);
  531.  
  532.     while (VALIDEDGE(area))
  533.     {
  534.  
  535.         count = 0;
  536.         y = area->ymin;
  537.  
  538.         do
  539.         {
  540.             next = area->link;
  541.  
  542.             if (ISDOWN(area->flag))
  543.                 newcount = count + 1;
  544.             else
  545.                 newcount = count - 1;
  546.  
  547.             if (count == 0 || newcount == 0)
  548.                 last = area;
  549.             else
  550.                 discard(last, next);
  551.  
  552.             count = newcount;
  553.             area = next;
  554.  
  555.         }
  556.         while (area != NULL && area->ymin == y);
  557.  
  558.         if (count != 0)
  559.             t1_abort("Unwind:  uneven edges");
  560.     }
  561. }
  562.  
  563.  
  564. /*
  565.  * "workedge" Array
  566.  *
  567.  * This is a statically allocated array where edges are built
  568.  * before being copied into more permanent storage by NewEdge().
  569.  */
  570.  
  571. #ifndef   MAXEDGE
  572. #define   MAXEDGE     1000
  573. #endif
  574.  
  575. static pel workedge[MAXEDGE];
  576. static pel *currentworkarea = workedge;
  577. static pel currentsize = MAXEDGE;
  578.  
  579.  
  580. /*
  581.  * ChangeDirection() - Called When Y Direction Changes
  582.  *
  583.  * The rasterizing routines call this entry point when they detect
  584.  * a change in Y.  We then build the current edge and sort it into
  585.  * emerging edgelist at 'anchor' by calling whatever "newedgefcn"
  586.  * is appropriate.
  587.  */
  588. void ChangeDirection(
  589.         int type,            /* CD_FIRST, CD_CONTINUE, or CD_LAST */
  590.         struct region *R,        /* region in which we are changing direction */
  591.         fractpel x, fractpel y,        /* current beginning x,y */
  592.         fractpel dy)            /* direction and magnitude of change in y */
  593. {
  594.     fractpel ymin, ymax;            /* minimum and maximum Y since last call */
  595.     fractpel x_at_ymin, x_at_ymax;        /* their respective X's */
  596.     pel iy;                    /* nearest integer pel to 'y' */
  597.     pel idy;                /* nearest integer pel to 'dy' */
  598.     int ydiff;                /* allowed Y difference in 'currentworkarea' */
  599.  
  600.     IfTrace4((RegionDebug > 0), "Change Y direction (%d) from (%p,%p), dy=%p\n",
  601.          (long)type, x, y, dy);
  602.  
  603.     if (type != CD_FIRST)
  604.     {
  605.  
  606.         if (R->lastdy > 0)
  607.         {
  608.             ymin = R->firsty;
  609.             x_at_ymin = R->firstx;
  610.             ymax = y;
  611.             x_at_ymax = x;
  612.         }
  613.         else
  614.         {
  615.             ymin = y;
  616.             x_at_ymin = x;
  617.             ymax = R->firsty;
  618.             x_at_ymax = R->firstx;
  619.         }
  620.  
  621.         if (ymax < ymin)
  622.             t1_abort("negative sized edge?");
  623.  
  624.  
  625. //        (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax,
  626. //                  R->lastdy > 0, x_at_ymin, x_at_ymax);
  627.         (*R->newedgefcn) (R, R->edgexmin, R->edgexmax, ymin, ymax,
  628.                   R->lastdy > 0);
  629.  
  630.     }
  631.  
  632.     R->firsty = y;
  633.     R->firstx = x;
  634.     R->lastdy = dy;
  635.  
  636.     iy = NEARESTPEL(y);
  637.     idy = NEARESTPEL(dy);
  638.     if (currentworkarea != workedge && idy < MAXEDGE && idy > -MAXEDGE)
  639.     {
  640.         NonObjectFree(currentworkarea);
  641.         currentworkarea = workedge;
  642.         currentsize = MAXEDGE;
  643.     }
  644.     ydiff = currentsize - 1;
  645.     if (dy > 0)
  646.     {
  647.         R->edge = ¤tworkarea[-iy];
  648.         R->edgeYstop = TOFRACTPEL(ydiff + iy) + FPHALF;
  649.     }
  650.     else
  651.     {
  652.         R->edge = ¤tworkarea[ydiff - iy];
  653.         R->edgeYstop = TOFRACTPEL(iy - ydiff) - FPHALF;
  654.     }
  655.     R->edgexmax = R->edgexmin = x;
  656.  
  657.     /*
  658.      * If this is the end of a subpath, we complete the subpath circular
  659.      * chain:
  660.      */
  661.     if (type == CD_LAST && R->lastedge != NULL)
  662.     {
  663.         register struct edgelist *e = R->firstedge;
  664.  
  665.         while (e->subpath != NULL)
  666.             e = e->subpath;
  667.         e->subpath = R->lastedge;
  668.         R->lastedge = R->firstedge = NULL;
  669.     }
  670. }
  671.  
  672.  
  673. /*
  674.  * newfilledge() - Called When We Have a New Edge While Filling
  675.  *
  676.  * This is the prototypical "newedge" function passed to "Rasterize" and
  677.  * stored in "newedgefcn" in the region being built.
  678.  *
  679.  * If the edge is non-null, we sort it onto the list of edges we are
  680.  * building at "anchor".
  681.  *
  682.  * This function also has to keep the bounding box of the region
  683.  * up to date.
  684.  */
  685. static void newfilledge(
  686.         struct region *R,        /* region being built */
  687.         fractpel xmin,
  688.         fractpel xmax,            /* X range of this edge */
  689.         fractpel ymin,
  690.         fractpel ymax,            /* Y range of this edge */
  691.         int isdown)            /* flag:  TRUE means edge goes down, else up */
  692. {
  693.     pel pelxmin, pelymin, pelxmax, pelymax;    /* pel versions of bounds */
  694.     struct edgelist *edge;            /* newly created edge */
  695.  
  696.     pelymin = NEARESTPEL(ymin);
  697.     pelymax = NEARESTPEL(ymax);
  698.     if (pelymin == pelymax)
  699.         return;
  700.  
  701.     pelxmin = NEARESTPEL(xmin);
  702.     pelxmax = NEARESTPEL(xmax);
  703.  
  704.     if (pelxmin < R->xmin)
  705.         R->xmin = pelxmin;
  706.     if (pelxmax > R->xmax)
  707.         R->xmax = pelxmax;
  708.     if (pelymin < R->ymin)
  709.         R->ymin = pelymin;
  710.     if (pelymax > R->ymax)
  711.         R->ymax = pelymax;
  712.  
  713.     edge = NewEdge(pelxmin, pelxmax, pelymin, pelymax, &R->edge[pelymin], isdown);
  714.     edge->subpath = R->lastedge;
  715.     R->lastedge = edge;
  716.     if (R->firstedge == NULL)
  717.         R->firstedge = edge;
  718.  
  719.     R->anchor = SortSwath(R->anchor, edge, swathxsort);
  720. }
  721.  
  722.  
  723. /*
  724.  * Sorting Edges
  725.  *
  726.  * SortSwath() - Vertically Sort an Edge into a Region
  727.  *
  728.  * This routine sorts an edge or a pair of edges into a growing region,
  729.  * so that the region maintains its top-to-bottom, left-to-right form.
  730.  * The rules for sorting horizontally may vary depending on what you
  731.  * are doing, but the rules for vertical sorting are always the same.
  732.  * This routine is passed an argument that is a function that will
  733.  * perform the horizontal sort on demand (for example, swathxsort() or
  734.  * SwathUnion()).
  735.  *
  736.  * This is a recursive routine.  A new edge (or edge pair) may overlap
  737.  * the list I am building in strange and wonderful ways.  Edges may
  738.  * cross.  When this happens, my strategy is to split the incoming edge
  739.  * (or the growing list) in two at that point, execute the actual sort on
  740.  * the top part of the split, and recursively call myself to figure out
  741.  * exactly where the bottom part belongs.
  742.  */
  743. #define   TOP(e)      ((e)->ymin)    /* the top of an edge (for readability    */
  744. #define   BOTTOM(e)   ((e)->ymax)    /* the bottom of an edge (for readability */
  745.  
  746. struct edgelist *SortSwath(
  747.         struct edgelist *anchor,            /* list being built */
  748.         struct edgelist *edge,                /* incoming edge or pair of edges */
  749.         struct edgelist *(*swathfcn) (struct edgelist *, struct edgelist *))    /* horizontal sorter */
  750. {
  751.     struct edgelist *before, *after;
  752.     struct edgelist base;
  753.  
  754.     if (RegionDebug > 0)
  755.     {
  756.         if (RegionDebug > 2)
  757.         {
  758.             IfTrace3(TRUE, "SortSwath(anchor=%z, edge=%z, fcn=%x)\n",
  759.                  anchor, edge, swathfcn);
  760.         }
  761.         else
  762.         {
  763.             IfTrace3(TRUE, "SortSwath(anchor=%x, edge=%x, fcn=%x)\n",
  764.                  anchor, edge, swathfcn);
  765.         }
  766.     }
  767.     if (anchor == NULL)
  768.         return (edge);
  769.  
  770.     before = &base;
  771.     before->ymin = before->ymax = MINPEL;
  772.     before->link = after = anchor;
  773.  
  774.     /*
  775.      * If the incoming edge is above the current list, we connect the current
  776.      * list to the bottom of the incoming edge.  One slight complication is
  777.      * if the incoming edge overlaps into the current list.  Then, we
  778.      * first split the incoming edge in two at the point of overlap and recursively
  779.      * call ourselves to sort the bottom of the split into the current list:
  780.      */
  781.     if (TOP(edge) < TOP(after))
  782.     {
  783.         if (BOTTOM(edge) > TOP(after))
  784.         {
  785.  
  786.             after = SortSwath(after, splitedge(edge, TOP(after)), swathfcn);
  787.         }
  788.         vertjoin(edge, after);
  789.         return (edge);
  790.     }
  791.  
  792.     /*
  793.      * At this point the top of edge is not higher than the top of the list,
  794.      * which we keep in 'after'.  We move the 'after' point down the list,
  795.      * until the top of the edge occurs in the swath beginning with 'after'.
  796.      *
  797.      * If the bottom of 'after' is below the bottom of the edge, we have to
  798.      * split the 'after' swath into two parts, at the bottom of the edge.
  799.      * If the bottom of 'after' is above the bottom of the swath,
  800.      */
  801.     while (VALIDEDGE(after))
  802.     {
  803.  
  804.         if (TOP(after) == TOP(edge))
  805.         {
  806.             if (BOTTOM(after) > BOTTOM(edge))
  807.                 vertjoin(after, splitedge(after, BOTTOM(edge)));
  808.             else if (BOTTOM(after) < BOTTOM(edge))
  809.             {
  810.                 after = SortSwath(after,
  811.                   splitedge(edge, BOTTOM(after)), swathfcn);
  812.             }
  813.             break;
  814.         }
  815.         else if (TOP(after) > TOP(edge))
  816.         {
  817.             IfTrace0((BOTTOM(edge) < TOP(after) && RegionDebug > 0),
  818.                  "SortSwath:  disjoint edges\n");
  819.             if (BOTTOM(edge) > TOP(after))
  820.             {
  821.                 after = SortSwath(after,
  822.                      splitedge(edge, TOP(after)), swathfcn);
  823.             }
  824.             break;
  825.         }
  826.         else if (BOTTOM(after) > TOP(edge))
  827.             vertjoin(after, splitedge(after, TOP(edge)));
  828.  
  829.         before = after;
  830.         after = after->link;
  831.     }
  832.  
  833.     /*
  834.      * At this point 'edge' exactly corresponds in height to the current
  835.      * swath pointed to by 'after'.
  836.      */
  837.     if (after != NULL && TOP(after) == TOP(edge))
  838.     {
  839.         before = (*swathfcn) (before, edge);
  840.         after = before->link;
  841.     }
  842.  
  843.     /*
  844.      * At this point 'after' contains all the edges after 'edge', and 'before'
  845.      * contains all the edges before.  Whew!  A simple matter now of adding
  846.      * 'edge' to the linked list in its rightful place:
  847.      */
  848.     before->link = edge;
  849.     if (RegionDebug > 1)
  850.     {
  851.         IfTrace3(TRUE, "SortSwath:  in between %x and %x are %x",
  852.              before, after, edge);
  853.         while (edge->link != NULL)
  854.         {
  855.             edge = edge->link;
  856.             IfTrace1(TRUE, " and %x", edge);
  857.         }
  858.         IfTrace0(TRUE, "\n");
  859.     }
  860.     else
  861.         for (; edge->link != NULL; edge = edge->link)
  862.         {;
  863.         }
  864.  
  865.     edge->link = after;
  866.     return (base.link);
  867. }
  868.  
  869.  
  870. /*
  871.  * splitedge() - Split an Edge or Swath in Two at a Given Y Value
  872.  *
  873.  * This function returns the edge or swath beginning at the Y value, and
  874.  * is guaranteed not to change the address of the old swath while splitting
  875.  * it.
  876.  */
  877. static struct edgelist *splitedge(
  878.         struct edgelist *list,    /* area to split */
  879.         pel y)            /* Y value to split list at */
  880. {
  881.     struct edgelist *new;        /* anchor for newly built list */
  882.     struct edgelist *last;        /* end of newly built list */
  883.     struct edgelist *r;        /* temp pointer to new structure */
  884.     struct edgelist *lastlist;    /* temp pointer to last 'list' value */
  885.  
  886.     IfTrace2((RegionDebug > 1), "splitedge of %x at %d ", list, (long)y);
  887.  
  888.     lastlist = new = NULL;
  889.  
  890.     while (list != NULL)
  891.     {
  892.         if (y < list->ymin)
  893.             break;
  894.         if (y >= list->ymax)
  895.             t1_abort("splitedge: above top of list");
  896.         if (y == list->ymin)
  897.             t1_abort("splitedge: would be null");
  898.  
  899.         r = (struct edgelist *)Allocate(sizeof(struct edgelist), list, 0);
  900.  
  901.         /*
  902.          * At this point 'r' points to a copy of the single structure at 'list'.
  903.          * We will make 'r' be the new split 'edgelist'--the lower half.
  904.          * We don't bother to correct 'xmin' and 'xmax', we'll take the
  905.          * the pessimistic answer that results from using the old values.
  906.          */
  907.         r->ymin = y;
  908.         r->xvalues = list->xvalues + (y - list->ymin);
  909.  
  910.         /*
  911.          * Note that we do not need to allocate new memory for the X values,
  912.          * they can remain with the old "edgelist" structure.  We do have to
  913.          * update that old structure so it is not as high:
  914.          */
  915.         list->ymax = y;
  916.  
  917.         /*
  918.          * Insert 'r' in the subpath chain:
  919.          */
  920.         r->subpath = list->subpath;
  921.         list->subpath = r;
  922.  
  923.         /*
  924.          * Now attach 'r' to the list we are building at 'new', and advance
  925.          * 'list' to point to the next element in the old list:
  926.          */
  927.         if (new == NULL)
  928.             new = r;
  929.         else
  930.             last->link = r;
  931.         last = r;
  932.         lastlist = list;
  933.         list = list->link;
  934.     }
  935.  
  936.     /*
  937.      * At this point we have a new list built at 'new'.  We break the old
  938.      * list at 'lastlist', and add the broken off part to the end of 'new'.
  939.      * Then, we return the caller a pointer to 'new':
  940.      */
  941.     if (new == NULL)
  942.         t1_abort("null splitedge");
  943.     lastlist->link = NULL;
  944.     last->link = list;
  945.     IfTrace1((RegionDebug > 1), "yields %x\n", new);
  946.     return (new);
  947. }
  948.  
  949.  
  950. /*
  951.  * vertjoin() - Join Two Disjoint Edge Lists Vertically
  952.  *
  953.  * The two edges must be disjoint vertically.
  954.  */
  955. static void vertjoin(struct edgelist *top, struct edgelist *bottom)
  956. {
  957.     if (BOTTOM(top) > TOP(bottom))
  958.         t1_abort("vertjoin not disjoint");
  959.  
  960.     for (; top->link != NULL; top = top->link)
  961.     {;
  962.     }
  963.  
  964.     top->link = bottom;
  965.     return;
  966. }
  967.  
  968.  
  969. /*
  970.  * swathxsort() - Sorting by X Values
  971.  *
  972.  * We need to sort 'edge' into its rightful
  973.  * place in the swath by X value, taking care that we do not accidentally
  974.  * advance to the next swath while searching for the correct X value.  Like
  975.  * all swath functions, this function returns a pointer to the edge
  976.  * BEFORE the given edge in the sort.
  977.  */
  978. static struct edgelist *swathxsort(
  979.         struct edgelist *before0,     /* edge before this swath */
  980.         struct edgelist *edge)        /* input edge */
  981. {
  982.     struct edgelist *before;
  983.     struct edgelist *after;
  984.     pel y;
  985.  
  986.     before = before0;
  987.     after = before->link;
  988.  
  989.     while (after != NULL && TOP(after) == TOP(edge))
  990.     {
  991.  
  992.         register pel *x1, *x2;
  993.  
  994.         y = TOP(edge);
  995.         x1 = after->xvalues;
  996.         x2 = edge->xvalues;
  997.  
  998.         while (y < BOTTOM(edge) && *x1 == *x2)
  999.         {
  1000.             x1++;
  1001.             x2++;
  1002.             y++;
  1003.         }
  1004.         if (y >= BOTTOM(edge))
  1005.         {
  1006.             edge->flag |= ISAMBIGUOUS(ON);
  1007.             after->flag |= ISAMBIGUOUS(ON);
  1008.             break;
  1009.         }
  1010.  
  1011.         if (*x1 >= *x2)
  1012.             break;
  1013.  
  1014.         before = after;
  1015.         after = after->link;
  1016.     }
  1017.  
  1018.     /*
  1019.      * At this point, 'edge' is between 'before' and 'after'.  If 'edge' didn't
  1020.      * cross either of those other edges, we would be done.  We check for
  1021.      * crossing.  If it does cross, we split the problem up by calling SortSwath
  1022.      * recursively with the part of the edge that is below the crossing point:
  1023.      */
  1024.     {
  1025.         register int h0, h;            /* height of edge--number of scans */
  1026.  
  1027.         h0 = h = BOTTOM(edge) - y;
  1028.         y -= TOP(edge);
  1029.  
  1030.         if (h0 <= 0)
  1031.         {
  1032.             IfTrace0((RegionDebug > 0), "swathxsort: exactly equal edges\n");
  1033.             return (before);
  1034.         }
  1035.  
  1036.         if (TOP(before) == TOP(edge))
  1037.             h -= crosses(h, &before->xvalues[y], &edge->xvalues[y]);
  1038.         if (after != NULL && TOP(after) == TOP(edge))
  1039.             h -= crosses(h, &edge->xvalues[y], &after->xvalues[y]);
  1040.  
  1041.         if (h < h0)
  1042.         {
  1043.             SortSwath(before0->link,
  1044.                   splitedge(edge, TOP(edge) + y + h),
  1045.                   swathxsort);
  1046.         }
  1047.     }
  1048.  
  1049.     return (before);
  1050. }
  1051.  
  1052.  
  1053. /*
  1054.  * SwathUnion() - Union Two Edges by X Value
  1055.  *
  1056.  * We have a left and right edge that must be unioned into a growing
  1057.  * swath.  If they are totally disjoint, they are just added in.  The
  1058.  * fun comes in they overlap the existing edges.  Then some edges
  1059.  * will disappear.
  1060.  */
  1061. struct edgelist *SwathUnion(
  1062.         struct edgelist *before0,     /* edge before the swath */
  1063.         struct edgelist *edge)        /* list of two edges to be unioned */
  1064. {
  1065.     int h;                    /* saves height of edge */
  1066.     struct edgelist *rightedge;        /* saves right edge of 'edge' */
  1067.     struct edgelist *before, *after;     /* edge before and after */
  1068.     int h0;                    /* saves initial height */
  1069.  
  1070.     IfTrace2((RegionDebug > 1), "SwathUnion entered, before=%x, edge=%x\n",
  1071.          before0, edge);
  1072.  
  1073.     h0 = h = edge->ymax - edge->ymin;
  1074.     if (h <= 0)
  1075.         t1_abort("SwathUnion:  0 height swath?");
  1076.  
  1077.     before = before0;
  1078.     after = before->link;
  1079.  
  1080.     while (after != NULL && TOP(after) == TOP(edge))
  1081.     {
  1082.         register struct edgelist *right;
  1083.  
  1084.         right = after->link;
  1085.         if (right->xvalues[0] >= edge->xvalues[0])
  1086.             break;
  1087.         before = right;
  1088.         after = before->link;
  1089.     }
  1090.  
  1091.     /*
  1092.      * This is the picture at this point.  'L' indicates a left hand edge,
  1093.      * 'R' indicates the right hand edge.
  1094.      * '<--->' indicates the degree of uncertainty as to its placement
  1095.      * relative to other edges:
  1096.      *
  1097.      *    before           after
  1098.      *      R            <---L---->  R             L   R    L   R
  1099.      *               <---L--->  <------R-------------------------->
  1100.      *                  edge
  1101.      *
  1102.      * In case the left of 'edge' touches 'before', we need to reduce
  1103.      * the height by that amount.
  1104.      */
  1105.     if (TOP(before) == TOP(edge))
  1106.         h -= touches(h, before->xvalues, edge->xvalues);
  1107.  
  1108.     rightedge = edge->link;
  1109.  
  1110.     if (after == NULL || TOP(after) != TOP(edge) ||
  1111.         after->xvalues[0] > rightedge->xvalues[0])
  1112.     {
  1113.         IfTrace2((RegionDebug > 1),
  1114.              "SwathUnion starts disjoint: before=%x after=%x\n",
  1115.              before, after);
  1116.  
  1117.         /*
  1118.          * On this side of the the above 'if', the new edge is disjoint from the
  1119.          * existing edges in the swath.  This is the picture:
  1120.          *
  1121.          *    before           after
  1122.          *      R                L    R     L   R    L   R
  1123.          *               L    R
  1124.          *              edge
  1125.          *
  1126.          * We will verify it remains disjoint for the entire height.  If the
  1127.          * situation changes somewhere down the edge, we split the edge at that
  1128.          * point and recursively call ourselves (through 'SortSwath') to figure
  1129.          * out the new situation:
  1130.          */
  1131.         if (after != NULL && TOP(after) == TOP(edge))
  1132.             h -= touches(h, rightedge->xvalues, after->xvalues);
  1133.         if (h < h0)
  1134.             SortSwath(before0->link, splitedge(edge, edge->ymin + h), t1_SwathUnion);
  1135.  
  1136.         /* go to "return" this edge pair; it is totally disjoint */
  1137.     }
  1138.     else
  1139.     {
  1140.         /*
  1141.          * At this point, at the 'else', we know that the
  1142.          * new edge overlaps one or more pairs in the existing swath.  Here is
  1143.          * a picture of our knowledge and uncertainties:
  1144.          *
  1145.          *    before       after
  1146.          *      R            L        R     L   R    L   R
  1147.          *             <---L--->   <---R------------------->
  1148.          *                edge
  1149.          *
  1150.          * We need to move 'after' along until it is to the right of the
  1151.          * right of 'edge'.  ('After' should always point to a left edge of a pair:)
  1152.          */
  1153.         register struct edgelist *left;    /* variable to keep left edge in */
  1154.  
  1155.         do
  1156.         {
  1157.             left = after;
  1158.             after = (after->link)->link;
  1159.  
  1160.         }
  1161.         while (after != NULL && TOP(after) == TOP(edge)
  1162.                && after->xvalues[0] <= rightedge->xvalues[0]);
  1163.  
  1164.         /*
  1165.          * At this point this is the picture:
  1166.          *
  1167.          *    before                 left        after
  1168.          *      R            L    R   L      R     L   R
  1169.          *             <---L--->        <---R--->
  1170.          *                edge
  1171.          *
  1172.          * We need to verify that the situation stays like this all the way
  1173.          * down the edge.  Again, if the
  1174.          * situation changes somewhere down the edge, we split the edge at that
  1175.          * point and recursively call ourselves (through 'SortSwath') to figure
  1176.          * out the new situation:
  1177.          */
  1178.         h -= crosses(h, left->xvalues, rightedge->xvalues);
  1179.         h -= crosses(h, edge->xvalues, ((before->link)->link)->xvalues);
  1180.  
  1181.         if (after != NULL && TOP(after) == TOP(edge))
  1182.  
  1183.             h -= touches(h, rightedge->xvalues, after->xvalues);
  1184.  
  1185.         IfTrace3((RegionDebug > 1),
  1186.           "SwathUnion is overlapped until %d: before=%x after=%x\n",
  1187.              (long)TOP(edge) + h, before, after);
  1188.  
  1189.         /*
  1190.          * OK, if we touched either of our neighbors we need to split at that point
  1191.          * and recursively sort the split edge onto the list.  One tricky part
  1192.          * is that when we recursively sort, 'after' will change if it was not
  1193.          * in our current swath:
  1194.          */
  1195.         if (h < h0)
  1196.         {
  1197.             SortSwath(before0->link,
  1198.                   splitedge(edge, edge->ymin + h),
  1199.                   t1_SwathUnion);
  1200.  
  1201.             if (after == NULL || TOP(after) != TOP(edge))
  1202.                 for (after = before0->link;
  1203.                      TOP(after) == TOP(edge);
  1204.                      after = after->link)
  1205.                 {;
  1206.                 }
  1207.         }
  1208.  
  1209.         /*
  1210.          * Now we need to augment 'edge' by the left and right of the overlapped
  1211.          * swath, and to discard all edges between before and after, because they
  1212.          * were overlapped and have been combined with the new incoming 'edge':
  1213.          */
  1214.         edge->xmin = MIN(edge->xmin, (before->link)->xmin);
  1215.         edge->xmax = MIN(edge->xmax, (before->link)->xmax);
  1216.         edgemin(h, edge->xvalues, (before->link)->xvalues);
  1217.         rightedge->xmin = MAX(rightedge->xmin, (left->link)->xmin);
  1218.         rightedge->xmax = MAX(rightedge->xmax, (left->link)->xmax);
  1219.         edgemax(h, rightedge->xvalues, (left->link)->xvalues);
  1220.         discard(before, after);
  1221.     }
  1222.     return (before);
  1223. }
  1224.  
  1225.  
  1226. /*
  1227.  * swathrightmost() - Simply Sorts New Edge to Rightmost of Swath
  1228.  *
  1229.  * Like all swath functions, this function returns a pointer to the edge
  1230.  * BEFORE the given edge in the sort.
  1231.  */
  1232. static struct edgelist *swathrightmost(
  1233.         struct edgelist *before,/* edge before this swath */
  1234.         struct edgelist *edge)    /* input edge */
  1235. {
  1236.     struct edgelist *after;
  1237.  
  1238.     after = before->link;
  1239.  
  1240.     while (after != NULL && TOP(after) == TOP(edge))
  1241.     {
  1242.         before = after;
  1243.         after = after->link;
  1244.     }
  1245.  
  1246.     return (before);
  1247.  
  1248. }
  1249.  
  1250.  
  1251. /*
  1252.  * touches() - Returns the Remaining Height When Two Edges Touch
  1253.  *
  1254.  * So, it will return 0 if they never touch.  Allows incredibly(?) mnemonic
  1255.  * if (touches(...)) construct.
  1256.  */
  1257. static int touches(int h, pel *left, pel *right)
  1258. {
  1259.     for (; h > 0; h--)
  1260.         if (*left++ >= *right++)
  1261.             break;
  1262.     return (h);
  1263. }
  1264.  
  1265.  
  1266. /*
  1267.  * crosses() - Returns the Remaining Height When Two Edges Cross
  1268.  *
  1269.  * So, it will return 0 if they never cross.
  1270.  */
  1271. static int crosses(int h, pel *left, pel *right)
  1272. {
  1273.     for (; h > 0; h--)
  1274.         if (*left++ > *right++)
  1275.             break;
  1276.     return (h);
  1277. }
  1278.  
  1279.  
  1280. /*
  1281.  * cedgemin() - Stores the Mininum of an Edge and an X Value
  1282.  */
  1283. static void cedgemin(int h, pel *e1, pel x)
  1284. {
  1285.     for (; --h >= 0; e1++)
  1286.         if (*e1 > x)
  1287.             *e1 = x;
  1288. }
  1289.  
  1290.  
  1291. /*
  1292.  * cedgemax() - Stores the Maximum of an Edge and an X Value
  1293.  */
  1294. static void cedgemax(int h, pel *e1, pel x)
  1295. {
  1296.     for (; --h >= 0; e1++)
  1297.         if (*e1 < x)
  1298.             *e1 = x;
  1299. }
  1300.  
  1301.  
  1302. /*
  1303.  * edgemin() - Stores the Mininum of Two Edges in First Edge
  1304.  */
  1305. static void edgemin(int h, pel *e1, pel *e2)
  1306. {
  1307.     for (; --h >= 0; e1++, e2++)
  1308.         if (*e1 > *e2)
  1309.             *e1 = *e2;
  1310. }
  1311.  
  1312.  
  1313. /*
  1314.  * edgemax() - Stores the Maximum of Two Edges in First Edge
  1315.  */
  1316. static void edgemax(int h, pel *e1, pel *e2)
  1317. {
  1318.     for (; --h >= 0; e1++, e2++)
  1319.         if (*e1 < *e2)
  1320.             *e1 = *e2;
  1321. }
  1322.  
  1323.  
  1324. /*
  1325.  * discard() - Discard All Edges Between Two Edges
  1326.  *
  1327.  * At first glance it would seem that we could discard an edgelist
  1328.  * structure merely by unlinking it from the list and freeing it.  You are
  1329.  * wrong, region-breath!  For performance, the X values associated with an
  1330.  * edge are allocated contiguously with it.  So, we free the X values when
  1331.  * we free a structure.  However, once an edge has been split, we are no
  1332.  * longer sure which control block actually is part of the memory block
  1333.  * that contains the edges.  Rather than trying to decide, we play it safe
  1334.  * and never free part of a region.
  1335.  *
  1336.  * So, to mark a 'edgelist' structure as discarded, we move it to the end
  1337.  * of the list and set ymin=ymax.
  1338.  */
  1339. static void discard(struct edgelist *left, struct edgelist *right)
  1340. {
  1341.     struct edgelist *beg, *end, *p;
  1342.  
  1343.     IfTrace2((RegionDebug > 0), "discard:  l=%x, r=%x\n", left, right);
  1344.  
  1345.     beg = left->link;
  1346.     if (beg == right)
  1347.         return;
  1348.  
  1349.     for (p = beg; p != right; p = p->link)
  1350.     {
  1351.         if (p->link == NULL && right != NULL)
  1352.             t1_abort("discard():  ran off end");
  1353.         IfTrace1((RegionDebug > 0), "discarding %x\n", p);
  1354.         p->ymin = p->ymax = 32767;
  1355.         end = p;
  1356.     }
  1357.  
  1358.     /*
  1359.      * now put the chain beg/end at the end of right, if it is not
  1360.      * already there:
  1361.      */
  1362.     if (right != NULL)
  1363.     {
  1364.         left->link = right;
  1365.         while (right->link != NULL)
  1366.             right = right->link;
  1367.         right->link = beg;
  1368.     }
  1369.     end->link = NULL;
  1370. }
  1371.  
  1372.  
  1373. /*
  1374.  * Changing the Representation of Regions
  1375.  *
  1376.  * For convenience and/or performance, we sometimes like to change the way
  1377.  * regions are represented.  This does not change the object itself, just
  1378.  * the representation, so these transformations can be made on a permanent
  1379.  * region.
  1380.  */
  1381. void MoveEdges(
  1382.         struct region *R,        /* region to modify */
  1383.         fractpel dx,
  1384.         fractpel dy)            /* delta X and Y to move edge list by */
  1385. {
  1386.     struct edgelist *edge;        /* for looping through edges */
  1387.  
  1388.     R->origin.x += dx;
  1389.     R->origin.y += dy;
  1390.     R->ending.x += dx;
  1391.     R->ending.y += dy;
  1392.     if (R->thresholded != NULL)
  1393.     {
  1394.         R->thresholded->origin.x -= dx;
  1395.         R->thresholded->origin.y -= dy;
  1396.     }
  1397.  
  1398.     /*
  1399.      * From now on we will deal with dx and dy as integer pel values:
  1400.      */
  1401.     dx = NEARESTPEL(dx);
  1402.     dy = NEARESTPEL(dy);
  1403.     if (dx == 0 && dy == 0)
  1404.         return;
  1405.  
  1406.     R->xmin += dx;
  1407.     R->xmax += dx;
  1408.     R->ymin += dy;
  1409.     R->ymax += dy;
  1410.  
  1411.     for (edge = R->anchor; VALIDEDGE(edge); edge = edge->link)
  1412.     {
  1413.         edge->ymin += dy;
  1414.         edge->ymax += dy;
  1415.         if (dx != 0)
  1416.         {
  1417.             register int h;        /* loop index; height of edge */
  1418.             register pel *Xp;    /* loop pointer to X values */
  1419.  
  1420.             edge->xmin += dx;
  1421.             edge->xmax += dx;
  1422.             for (Xp = edge->xvalues, h = edge->ymax - edge->ymin;
  1423.                  --h >= 0;)
  1424.                 *Xp++ += dx;
  1425.         }
  1426.     }
  1427. }
  1428.  
  1429.  
  1430. /*
  1431.  * UnJumble() - Sort a Region Top to Bottom
  1432.  *
  1433.  * It is an open question whether it pays in general to do this.
  1434.  */
  1435. void UnJumble(struct region *region)
  1436. {
  1437.     struct edgelist *anchor;    /* new lists built here */
  1438.     struct edgelist *edge;        /* edge pointer for loop */
  1439.     struct edgelist *next;        /* ditto */
  1440.  
  1441.     anchor = NULL;
  1442.  
  1443.     for (edge = region->anchor; VALIDEDGE(edge); edge = next)
  1444.     {
  1445.         if (edge->link == NULL)
  1446.             t1_abort("UnJumble:  unpaired edge?");
  1447.         next = edge->link->link;
  1448.         edge->link->link = NULL;
  1449.         anchor = SortSwath(anchor, edge, t1_SwathUnion);
  1450.     }
  1451.  
  1452.     if (edge != NULL)
  1453.         vertjoin(anchor, edge);
  1454.  
  1455.     region->anchor = anchor;
  1456.     region->flag &= ~ISJUMBLED(ON);
  1457. }
  1458.  
  1459.  
  1460. static void OptimizeRegion(struct region *R)
  1461. {
  1462.     pel *xP;            /* pel pointer for inner loop */
  1463.     int x;                /* holds X value */
  1464.     int xmin, xmax;        /* holds X range */
  1465.     int h;                /* loop counter */
  1466.     struct edgelist *e;    /* edgelist pointer for loop */
  1467.  
  1468.     R->flag |= ISRECTANGULAR(ON);
  1469.  
  1470.     for (e = R->anchor; VALIDEDGE(e); e = e->link)
  1471.     {
  1472.         xmin = MAXPEL;
  1473.         xmax = MINPEL;
  1474.         for (h = e->ymax - e->ymin, xP = e->xvalues; --h >= 0;)
  1475.         {
  1476.             x = *xP++;
  1477.             if (x < xmin)
  1478.                 xmin = x;
  1479.             if (x > xmax)
  1480.                 xmax = x;
  1481.         }
  1482.         if (xmin != xmax || (xmin != R->xmin && xmax != R->xmax))
  1483.             R->flag &= ~ISRECTANGULAR(ON);
  1484.         if (xmin < e->xmin || xmax > e->xmax)
  1485.             t1_abort("Tighten: existing edge bound was bad");
  1486.         if (xmin < R->xmin || xmax > R->xmax)
  1487.             t1_abort("Tighten: existing region bound was bad");
  1488.         e->xmin = xmin;
  1489.         e->xmax = xmax;
  1490.     }
  1491.     R->flag |= ISOPTIMIZED(ON);
  1492. }
  1493.  
  1494.  
  1495. /*
  1496.  * Miscellaneous Routines
  1497.  *
  1498.  * MoreWorkArea() - Allocate New Space for "edge"
  1499.  *
  1500.  * Our strategy is to temporarily allocate an array to hold this
  1501.  * unexpectedly large edge.  ChangeDirection frees this array any time
  1502.  * it gets a shorter 'dy'.
  1503.  */
  1504. void MoreWorkArea(
  1505.         struct region *R,            /* region we are generating */
  1506.         fractpel x1, fractpel y1,    /* starting point of line */
  1507.         fractpel x2, fractpel y2)    /* ending point of line */
  1508. {
  1509.     int idy;    /* integer dy of line */
  1510.  
  1511.     idy = NEARESTPEL(y1) - NEARESTPEL(y2);
  1512.     if (idy < 0)
  1513.         idy = -idy;
  1514.  
  1515.     /*
  1516.      * we must add one to the delta for the number of run ends we
  1517.      * need to store:
  1518.      */
  1519.     if (++idy > currentsize)
  1520.     {
  1521.         IfTrace1((RegionDebug > 0), "Allocating edge of %d pels\n", idy);
  1522.         if (currentworkarea != workedge)
  1523.             NonObjectFree(currentworkarea);
  1524.         currentworkarea = (pel *) Allocate(0, NULL, idy * sizeof(pel));
  1525.         currentsize = idy;
  1526.     }
  1527.     ChangeDirection(CD_CONTINUE, R, x1, y1, y2 - y1);
  1528. }
  1529.  
  1530.  
  1531. /*
  1532.  * BoxClip() - Clip a Region to a Rectangle
  1533.  *
  1534.  * BoxClip also duplicates the region if it is permanent.  Note the
  1535.  * clipping box is specified in REGION coordinates, that is, in
  1536.  * coordinates relative to the region (0,0) point
  1537.  */
  1538. struct region *BoxClip(
  1539.         struct region *R,        /* region to clip */
  1540.         pel xmin, pel ymin,        /* upper left hand corner of rectangle */
  1541.         pel xmax, pel ymax)        /* lower right hand corner */
  1542. {
  1543.     struct edgelist anchor;        /* pretend edgelist to facilitate discards */
  1544.     struct edgelist *e, *laste;
  1545.  
  1546.     IfTrace1((OffPageDebug), "BoxClip of %z:\n", R);
  1547.  
  1548.     R = UniqueRegion(R);
  1549.  
  1550.     if (xmin > R->xmin)
  1551.     {
  1552.         IfTrace2((OffPageDebug), "BoxClip:  left clip old %d new %d\n",
  1553.              (long)R->xmin, (long)xmin);
  1554.         R->xmin = xmin;
  1555.     }
  1556.     if (xmax < R->xmax)
  1557.     {
  1558.         IfTrace2((OffPageDebug), "BoxClip:  right clip old %d new %d\n",
  1559.              (long)R->xmax, (long)xmax);
  1560.         R->xmax = xmax;
  1561.     }
  1562.  
  1563.     if (ymin > R->ymin)
  1564.     {
  1565.         IfTrace2((OffPageDebug), "BoxClip:  top clip old %d new %d\n",
  1566.              (long)R->ymin, (long)ymin);
  1567.         R->ymin = ymin;
  1568.     }
  1569.     if (ymax < R->ymax)
  1570.     {
  1571.         IfTrace2((OffPageDebug), "BoxClip:  bottom clip old %d new %d\n",
  1572.              (long)R->ymax, (long)ymax);
  1573.         R->ymax = ymax;
  1574.     }
  1575.  
  1576.     laste = &anchor;
  1577.     anchor.link = R->anchor;
  1578.  
  1579.     for (e = R->anchor; VALIDEDGE(e); e = e->link)
  1580.     {
  1581.         if (TOP(e) < ymin)
  1582.         {
  1583.             e->xvalues += ymin - e->ymin;
  1584.             e->ymin = ymin;
  1585.         }
  1586.         if (BOTTOM(e) > ymax)
  1587.             e->ymax = ymax;
  1588.         if (TOP(e) >= BOTTOM(e))
  1589.         {
  1590.             discard(laste, e->link->link);
  1591.             e = laste;
  1592.             continue;
  1593.         }
  1594.         if (e->xmin < xmin)
  1595.         {
  1596.             cedgemax(BOTTOM(e) - TOP(e), e->xvalues, xmin);
  1597.             e->xmin = xmin;
  1598.             e->xmax = MAX(e->xmax, xmin);
  1599.         }
  1600.         if (e->xmax > xmax)
  1601.         {
  1602.             cedgemin(BOTTOM(e) - TOP(e), e->xvalues, xmax);
  1603.             e->xmin = MIN(e->xmin, xmax);
  1604.             e->xmax = xmax;
  1605.         }
  1606.         laste = e;
  1607.     }
  1608.  
  1609.     R->anchor = anchor.link;
  1610.  
  1611.     return (R);
  1612. }
  1613.  
  1614.  
  1615. #ifdef notdef
  1616. /*
  1617.  * CoerceRegion() - Force a TextPath Structure to Become a Region
  1618.  *
  1619.  * We also save the newly created region in the textpath structure, if the
  1620.  * structure was permanent.  Then we don't have to do this again.  Why not
  1621.  * save it all the time?  Well, we certainly could, but I suspect it
  1622.  * wouldn't pay.  We would have to make this region permanent (because we
  1623.  * couldn't have it be consumed) and this would probably require
  1624.  * unnecessary CopyRegions in most cases.
  1625.  */
  1626. struct region *CoerceRegion(
  1627.         struct textpath *tp)    /* input TEXTTYPE */
  1628. {
  1629.     struct segment *path;        /* temporary character path */
  1630.     struct region *R;            /* returned region */
  1631.  
  1632.     R = Interior(path, EVENODDRULE);
  1633.     return (R);
  1634. }
  1635. #endif
  1636.  
  1637.  
  1638. /*
  1639.  * RegionBounds() - Returns Bounding Box of a Region
  1640.  */
  1641. struct segment *t1_RegionBounds(struct region *R)
  1642. {
  1643.     extern struct XYspace *IDENTITY;
  1644.  
  1645.     struct segment *path;    /* returned path */
  1646.  
  1647.     path = BoxPath(IDENTITY, R->ymax - R->ymin, R->xmax - R->xmin);
  1648.     path = Join(PathSegment(MOVETYPE, R->origin.x + TOFRACTPEL(R->xmin),
  1649.                 R->origin.y + TOFRACTPEL(R->ymin)),
  1650.             path);
  1651.     return (path);
  1652. }
  1653.  
  1654.  
  1655. /*
  1656.  * Formatting/Dump Routines for Debug
  1657.  *
  1658.  * DumpArea() - Display a Region
  1659.  */
  1660. void DumpArea(struct region *area)
  1661. {
  1662.     IfTrace1(TRUE, "Dumping area %x,", area);
  1663.     IfTrace4(TRUE, " X %d:%d Y %d:%d;", (long)area->xmin,
  1664.          (long)area->xmax, (long)area->ymin, (long)area->ymax);
  1665.     IfTrace4(TRUE, " origin=(%p,%p), ending=(%p,%p)\n",
  1666.         area->origin.x, area->origin.y, area->ending.x, area->ending.y);
  1667.     DumpEdges(area->anchor);
  1668. }
  1669.  
  1670.  
  1671. #define  INSWATH(p, y0, y1)  (p != NULL && p->ymin == y0 && p->ymax == y1)
  1672.  
  1673.  
  1674. /*
  1675.  * DumpEdges() - Display Run End Lists (Edge Lists)
  1676.  */
  1677. static pel RegionDebugYMin = MINPEL;
  1678. static pel RegionDebugYMax = MAXPEL;
  1679.  
  1680. void DumpEdges(struct edgelist *edges)
  1681. {
  1682.     struct edgelist *p, *p2;
  1683.     pel ymin = MINPEL;
  1684.     pel ymax = MINPEL;
  1685.     int y;
  1686.  
  1687.     if (edges == NULL)
  1688.     {
  1689.         IfTrace0(TRUE, "    NULL area.\n");
  1690.         return;
  1691.     }
  1692.     if (RegionDebug <= 1)
  1693.     {
  1694.         for (p = edges; p != NULL; p = p->link)
  1695.         {
  1696.             edgecheck(p, ymin, ymax);
  1697.             ymin = p->ymin;
  1698.             ymax = p->ymax;
  1699.             IfTrace3(TRUE, ". at %x type=%d flag=%x",
  1700.                  p, (long)p->type, (long)p->flag);
  1701.             IfTrace4(TRUE, " bounding box HxW is %dx%d at (%d,%d)\n",
  1702.                  (long)ymax - ymin, (long)p->xmax - p->xmin,
  1703.                  (long)p->xmin, (long)ymin);
  1704.         }
  1705.     }
  1706.     else
  1707.     {
  1708.  
  1709.         for (p2 = edges; p2 != NULL;)
  1710.         {
  1711.  
  1712.             edgecheck(p2, ymin, ymax);
  1713.             ymin = p2->ymin;
  1714.             ymax = p2->ymax;
  1715.  
  1716.             if (RegionDebug > 3 || (ymax > RegionDebugYMin
  1717.                         && ymin < RegionDebugYMax))
  1718.             {
  1719.                 IfTrace2(TRUE, ". Swath from %d to %d:\n",
  1720.                      ymin, ymax);
  1721.                 for (p = p2; INSWATH(p, ymin, ymax); p = p->link)
  1722.                 {
  1723.                     IfTrace4(TRUE, ". . at %x[%x] range %d:%d, ",
  1724.                          p, (long)p->flag,
  1725.                           (long)p->xmin, (long)p->xmax);
  1726.                     IfTrace1(TRUE, "subpath=%x,\n", p->subpath);
  1727.                 }
  1728.             }
  1729.             for (y = MAX(ymin, RegionDebugYMin); y < MIN(ymax, RegionDebugYMax); y++)
  1730.             {
  1731.                 IfTrace1(TRUE, ". . . Y[%5d] ", (long)y);
  1732.                 for (p = p2; INSWATH(p, ymin, ymax); p = p->link)
  1733.                     IfTrace1(TRUE, "%5d ",
  1734.                          (long)p->xvalues[y - ymin]);
  1735.                 IfTrace0(TRUE, "\n");
  1736.             }
  1737.             while (INSWATH(p2, ymin, ymax))
  1738.                 p2 = p2->link;
  1739.         }
  1740.     }
  1741. }
  1742.  
  1743.  
  1744. /*
  1745.  * edgecheck() - For Debug, Verify that an Edge Obeys the Rules
  1746.  */
  1747. static void edgecheck(struct edgelist *edge, int oldmin, int oldmax)
  1748. {
  1749.     if (edge->type != EDGETYPE)
  1750.         t1_abort("EDGE ERROR: non EDGETYPE in list");
  1751.     /*
  1752.      * The following check is not valid if the region is jumbled so I took it
  1753.      * out:
  1754.      */
  1755. /*     if (edge->ymin < oldmax && edge->ymin != oldmin)
  1756.                t1_abort("EDGE ERROR: overlapping swaths"); */
  1757. }
  1758.